package com.test.daily.leetcode.y2022.m06.day0613.v01;

/**
 * @descriptions: Solution
 * @author: Tom
 * @date: 2022/6/13 上午 09:54
 * @version: 1.0
 */
public class Solution {
    public static int min(int[] arr, int aim){
        return process( arr, aim, 0);
    }
    public static int process(int[] arr, int rest, int index){
       if(index == arr.length){
           return rest == 0 ? 1: Integer.MAX_VALUE;
       } else {
           int ans = Integer.MAX_VALUE;
           for(int zhang = 0; zhang*arr[index] >= rest; zhang++){
                int next =process(arr, rest-zhang*arr[index], index+1);
                if (next != Integer.MAX_VALUE){
                    ans = Math.min(ans, zhang + next);
                }
           }
           return ans;
       }
    }
    public static int dp1(int[] arr, int aim){
        int N = arr.length;
        int[][] dp = new int[N+1][aim+1];
//        for (int i = 0; i < N + 1; i++) {
//            for(int j = 0; j < aim + 1; j++){
//                dp[i][j] = Integer.MAX_VALUE;
//            }
//        }
        dp[N][0] = 1;
        for(int index = N-1; index >=0; index--){
            for(int rest = 0; rest <= aim; rest++){
                int ans = Integer.MAX_VALUE;
                for(int zhang = 0; arr[index]* zhang <= rest; zhang++){
                    int next = dp[index][rest-arr[index]*zhang];
                    if(next != Integer.MAX_VALUE){
                        ans = Math.min(ans, dp[index+1][rest-arr[index]*zhang]);
                    }
                }
                dp[index][rest] = ans;
            }
        }
        return dp[0][aim];
    }

    public static int dp2(int[] arr, int aim){
        int N = arr.length;
        int[][] dp = new int[N+1][aim+1];
        dp[N][0] = 1;
        for(int j = 1; j < aim + 1; j++){
            dp[N][j] = Integer.MAX_VALUE;
        }
        for(int index = N; index >= 0; index-- ){
            for(int rest = 0; rest <= aim; rest++){
                dp[index][rest] = dp[index+1][rest];
                if(rest - arr[index] > 0 && dp[index][rest-arr[index]] != Integer.MAX_VALUE){
                    dp[index][rest] = Math.min(dp[index][rest], dp[index][rest-arr[index]] + 1);
                }
            }
        }
        return dp[0][aim];
    }
}














